package consistenthash

import (
	"fmt"
	"hash/crc32"
	"sort"
	"strconv"
)

// 一致性哈希


// 自定义的Hash函数
type Hash func(key []byte) uint32


type Map struct {
	// hash函数
	hash Hash
	// 每个真实节点的虚拟节点数量
	replicas int
	// 哈希环
	keys []int
	// 虚拟节点与真实节点的映射表 (虚拟节点哈希值 -> 真实节点名称)
	haspMap map[int]string
}


func New(replicas int, fn Hash) *Map{
	m := &Map{
		hash: fn,
		replicas: replicas,
		haspMap: make(map[int]string),
	}

	// 默认hash算法
	if fn == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}


// 添加节点
func (m *Map) Add(keys ...string) {
	for _, key := range(keys) {
		// 生成虚拟节点
		for i := 0; i < m.replicas; i++ {
			// 计算当前节点hash
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			// 添加到哈希环中
			m.keys = append(m.keys, hash)
			// 虚拟节点hash到真实节点名称的映射
			m.haspMap[hash] = key
		}
	}

	// 最后将所有节点进行排序
	sort.Ints(m.keys)
}


// 通过key获取所在的真实节点名称
func (m *Map) Get(key string) string{
	if len(m.keys) == 0 {
		return ""
	}

	// 计算当前key的hash
	hash := int(m.hash([]byte(key)))

	// 顺时针查找第一个匹配的虚拟节点的下标
	// sort.Search基于二分查找, 从0 ~ len(m.keys)中查找第一个func方法return True的值
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})

	// 返回真实节点名称
	// 当sort.Search未找到时, idx会比len(m.keys)大, 因此需要取模一下
	return m.haspMap[m.keys[idx%len(m.keys)]]
}


func (m *Map) PrintKeys() {
	fmt.Printf("keys: %v\n", m.keys)
}


func (m *Map) PrintHashMap() {
	fmt.Printf("hashMap: %v\n", m.haspMap)
}